package com.base.datastructer.tree;


public class BinaryTree {
    public static String LEFT_NODE_RIGHT = "left_node_right";
    public static String RIGHT_NODE_LEFT = "right_node_left";
    
    public static String LEFT_RIGHT_NODE = "left_right_node";
    public static String RIGHT_LEFT_NODE = "right_left_node";
    
    public static String NODE_LEFT_RIGHT = "node_left_right";
    public static String NODE_RIGHT_LEFT = "node_right_left";
    
    private TreeNode rootNode;
    
    public BinaryTree(){
        this.rootNode = null;
    }
    
    public TreeNode getRootNode(){
        return rootNode;
    }
    
    public void addLeaf(TreeNode newNode){
        // 1. If the tree is empty
        if(this.rootNode == null){
            this.rootNode = newNode;
        } else {
            
            TreeNode focusNode = this.rootNode;
            TreeNode parent;
            
            while(true){
                parent = focusNode;
                
                if(newNode.getData() < focusNode.getData()){
                    focusNode = focusNode.getpLeft();
                    if(focusNode == null){
                        parent.setpLeft(newNode); 
                        return;
                    }
                } else {
                    focusNode = focusNode.getPRight();
                    if(focusNode == null){
                        parent.setPRight(newNode);
                        return;
                    }
                }
            }
        }
    }
    public void printTree(String type){
        
        if(LEFT_NODE_RIGHT.equals(type)){
            printTreeLNR(this.rootNode);
        } else if(LEFT_RIGHT_NODE.equals(type)) {
            printTreeLRN(this.rootNode);
        } else if(NODE_LEFT_RIGHT.equals(type)) {
            printTreeNLR(this.rootNode);
        } else if(RIGHT_NODE_LEFT.equals(type)) {
            
        } else if(RIGHT_LEFT_NODE.equals(type)) {
            
        } else if(NODE_RIGHT_LEFT.equals(type)) {
            
        }
        
    }
    private void printTreeLNR(TreeNode node){
        if(node == null){
        	return;
        }
        printTreeLNR(node.getpLeft());
        node.printInfoNode();
        printTreeLNR(node.getPRight());
        
    }
    
    private void printTreeLRN(TreeNode node){
        if(node == null){
        	return;
        }
        printTreeLNR(node.getpLeft());
        printTreeLNR(node.getPRight());
        node.printInfoNode();
        
    }
    
    private void printTreeNLR(TreeNode node){
        if(node == null){
        	return;
        }
        node.printInfoNode();
        printTreeLNR(node.getpLeft());
        printTreeLNR(node.getPRight());
        
    }
    
    public int countNode(TreeNode t){
    	if(t == null){
    		return 0;
    	}
    	int left = countNode(t.getpLeft());
    	int right = countNode(t.getPRight());
    	return left + right + 1;
    }
    
    public TreeNode findNode(TreeNode t ,int x){
    	if(t == null){
    		return null;
    	}
    	if(t.getData() == x ){
    		return t;
    	}
    	TreeNode left = findNode(t.getpLeft(),x);
    	if(left != null){
    		return left;
    	}
    	TreeNode right = findNode(t.getPRight(),x);
    	if(right != null){
    		return right;
    	}
    	return null;
    }
    
    public TreeNode findMax(TreeNode t){
    	if(t == null){
    		return null;
    	}
    
    	TreeNode left = findMax(t.getpLeft());
    	TreeNode right = findMax(t.getPRight());
    	
    	TreeNode lc = t;
    	if(left != null && left.getData() > lc.getData()){
    		lc = left;
    	}
    	
    	if(right != null && right.getData() > lc.getData()){
    		lc = right;
    	}
    	return lc;
    }
    
    public int heightTree(TreeNode t){
    	if( t == null){
    		return 0;
    	}
    	int heightLeft = heightTree(t.getpLeft());
    	int heightRight = heightTree(t.getPRight());
    	if(heightLeft > heightRight){
    		return heightLeft + 1;
    	}
    	return heightRight + 1;
    }
    
    //dem so luong node tren tang k cua cay
    
    public int countLevel(TreeNode t,int k){
    	
    	if(t == null){
    		return 0;
    	}
    	
    	if(k == 0){
    		if(t.getData() < 0 ){
    			return 1;
    		}
    		return 0;
    	}
    	
    	int left = countLevel(t.getpLeft(),k-1);
    	int right = countLevel(t.getPRight(),k-1);
    	
    	return left + right;
    }
}
